This invention relates to routing, wavelength assignment, network design, and reconfiguration for optical wavelength-division-multiplexed (WDM) networks.
Communication networks can make use of optical communication links between nodes of a network in order to provide a higher communication capacity between nodes than may be available using electrical communication links. For example, a data stream may be used to modulate an optical signal for transmission over a link. At the receiving node the data stream is demodulated to form an electrical signal. The data stream that is encoded in the demodulated electrical signal is then routed to an outgoing optical link where it is used to modulate an outbound optical signal. The maximum data rate of a signal that is routed in such a manner is typically in the order of 10 Gb/s.
More recently, optical links have been used to carry a number of data streams in a frequency multiplexing approach in which each of a number of optical signals at different wavelengths are modulated by different data streams. This approach is known as “wavelength division multiplexing (WDM).” For example, this approach provides an aggregate capacity on each optical fiber that can be in the order of 2 Tb/s using 1000 different wavelengths each carrying a 2 Gb/s data stream. At nodes in the network, one approach to routing data is to optically demultiplex the separate optical signals that arrive at an input port and demodulate each data stream to form an electrical signal. The electrical signals carrying the data streams are then electrically routed to appropriate output ports, where the outbound data streams modulate different wavelength optical signals and the modulated optical signals are multiplexed for transmission over the outbound optical fibers. Certain nodes, called access nodes or access stations, provide interfaces for data signals passing to or from the network, while intermediate routing nodes pass the optical signals between links within the network.
Rather than routing optical signals at intermediate nodes by converting the data streams to electrical signals, all-optical networks have been developed in which optical signals are passed between ports of intermediate nodes without electrical conversion. In such a network, a node can perform wavelength routing in which the node is configured such that optical signals are routed between particular ports of the node according to their wavelengths without conversion to electrical signals. For instance, the node can be configured such that optical signals arriving at a port at different wavelengths are routed to other ports according to their wavelengths. The configuration of such a wavelength routing node can be static, or can be reconfigurable. Furthermore, a reconfigurable wavelength routing node may allow any combination of routing patterns, or may be constrained, for example by the physical design of the wavelength router, to only allow a subset of routing patterns.
In addition to routing optical signals according to their wavelengths, wavelength conversion devices are available that can change the frequency of an optical signal as it passes through a node. A node that includes both wavelength conversion and wavelength routing capabilities can route optical signals arriving at one wavelength at one port to a different wavelength on another port. As with wavelength routers, wavelength conversion can be static or reconfigurable, and if reconfigurable, may be limited to only a subset of all combinations of wavelength conversion.
In general, the flexibility of static or configurable wavelength routing and wavelength conversion comes at a financial cost and may also result in degradation of optical signals as they pass through the node, thereby limiting data rates or ranges over which optical signals can be transmitted through the network.
An all-optical wavelength routed network allows high data rates to pass between origin-destination pairs of access nodes without electrical conversion at intermediate routing nodes along a path joining the origin-destination pair in the network. A continuous lightpath is set up between a pair of access nodes by configuring the intermediate routing nodes to pass the lightpath along links of the network joining the access nodes. In the absence of wavelength conversion, a lightpath occupies the same wavelength on all fiber links on the lightpath. This is often referred to as wavelength continuity on a lightpath.
If the network supports wavelength conversion in addition to wavelength routing, a lightpath may change wavelength at intermediate nodes along its route and therefore may have different wavelengths on different links along its path. If the routing nodes are reconfigurable, different lightpaths can be established and terminated on an ongoing basis, for example, as the demand for communication capacity between different pairs of access nodes changes.
Establishing a lightpath for a communication session between two access nodes involves both determining a path in the network between the two access nodes and allocating a free wavelength on each of the links on that path. Intermediate routing nodes are then configured to optically couple appropriate wavelengths between successive links on the path to provide a continuous all-optical path between the access nodes. Once established, the entire bandwidth on the lightpath is reserved for this communication session between access nodes until it is terminated, at which time the associated wavelengths become available on all the links along the path.
Assignment of lightpaths to a set of desired connections between pairs of access nodes requires both assignment of a path through the network for each connection, and assignment of a wavelength to each link in each path. It is often desirable to select the assigned routes and wavelength to optimize a particular performance metric. This selection is known as the “routing and wavelength assignment (RWA)” problem. Numerous research studies have been conducted on the RWA problem. Several RWA schemes have been proposed that differ in the assumptions on the traffic pattern, availability of the wavelength converters, and desired objectives. The traffic assumptions generally fall into one of two categories: static or dynamic. In static RWA models the demand is assumed to be fixed and known. That is, all the lightpaths that are to be set up in the network are known beforehand. A typical objective is to accommodate the demand for lightpaths while minimizing the number of wavelengths used on all links. By contrast, in a stochastic/dynamic setting, lightpath requests between source-destination pairs are assumed to arrive one by one at random, and have random terminating times. A typical objective in this case is to minimize the blocking probability for new requests, or the total (perhaps weighted) number of blocked requests over a given period of time.
The RWA problem is critically important in increasing the efficiency of wavelength-routed optical networks. With a good solution of this problem, more customers can be statically accommodated by the given system. In dynamic systems, fewer requests to establish lightpaths are rejected during periods of congestion.
Even in the static case, the typically proposed formulations for optimal lightpath establishment require solution of difficult mixed integer linear programs. In particular, the optimal static lightpath establishment problem without wavelength converters was proven to be NP-complete by showing the equivalence of the problem to the graph-coloring problem. Since the associated integer linear programs are very hard to solve, corresponding relaxed linear programs in which the optimization variables are not required to be integral have been used to get bounds on the desired objective function. Alternative formulations of such relaxed problems have been considered to get tighter bounds. The usefulness of these bounds lies in the fact that they can be used as benchmarks against which performance of various heuristic RWA algorithms can be compared. However, there is no general way of converting an optimal non-integer solution to an optimal integer one.
Due to computational complexity of obtaining an optimal solution to the RWA problem, much of the previous work on the RWA problem has focused on developing efficient heuristic methods. A common approach is to decouple the routing and wavelength assignment steps by first finding a route from a predetermined set of candidate paths for all requested paths and then searching for an appropriate wavelength assignment for each route. However, given that the number of wavelengths is restricted and wavelength converters may not be available at all nodes, a suitable wavelength may not be available on all the links along a chosen route.
Recent work in WDM networks is based on a maximum-load model. In the maximum-load model, the route of each request is given and the problem is to find the minimum number of wavelengths to satisfy a given request set. This is a worst-case model, where no blocking of lightpaths is allowed, and there are no assumptions made on the traffic pattern. The traffic is characterized only by its load, which is the maximum number of lightpaths that can be present over any link in the network. However, this approach to designing a network can result in over-designing the network and using many wavelengths to support a typical request patterns.
Most of the literature on the RWA problem considers either networks without any wavelength converters or networks with wavelength converters at every node. The benefits of wavelength conversion have been analyzed under different traffic models. However, the high cost of full wavelength conversion at every node has led to research on networks with sparse wavelength conversion. In a network with sparse wavelength conversion, only a fraction of the nodes are equipped with wavelength converters.